#include <iostream>
#include <cstdlib>
#include <vector>
#include <omp.h>
#include <sys/resource.h>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;


void printElapsed (char *desc, struct timeval *start, struct timeval *end, int niters )
{
	struct timeval elapsed;
	if (start -> tv_usec > end -> tv_usec)
	{
		end -> tv_usec += 1000000;
		end -> tv_sec--;
	}

	elapsed.tv_usec = end -> tv_usec - start -> tv_usec;
	elapsed.tv_sec = end -> tv_sec - start -> tv_sec;

	printf("\n %s total elapsed time = %1d (usec)",
			 desc, (elapsed.tv_sec*1000000 + elapsed.tv_usec)/niters);

}/* printElapsed() */

int randomRange( int low, int high )
{
	double r = rand() / static_cast<float>(RAND_MAX);  
    int range = high - low;
    return static_cast<int>(random() * range) + low ;
}
double realrand()
{
	return rand () / (double) (RAND_MAX);
	//return (randomRange(0, 1));
}
/*The computing domain is bounded by [0, 1]*/
void generate_sites (unsigned num_sites, vector <double> & sites)
{

	for (int i = 0; i < num_sites; ++i)
	{
		sites.push_back (realrand());
	}
}

void training(vector <double> & sites, double error)
{
	vector <int> weights (sites.size(), 1);
	for (int i = 0; i < 100 ; ++i)
	{
		double q = realrand();
		//cout<<"SEED "<< q << endl;
		vector<double>::iterator low; 
		low = lower_bound (sites.begin(), sites.end(), q);
		unsigned pos =  unsigned (low - sites.begin());
		if (0 == pos || sites.size() -1 == pos) 
			;
		else 
		{
			if (abs(sites[pos-1] -q ) < abs (sites[pos] - q)) 
				pos = pos -1;
		}
		sites[pos] = (sites[pos] * weights[pos] + q) / (weights[pos] + 1);
		weights[pos] ++;
	}
	for (int i = 0; i < weights.size(); ++i)
	{
		cout<< weights[i] <<endl;
	}
	cout<<endl;
}
int main()
{
	vector <double> sites;
	srand(11);
	generate_sites (10, sites);
	sort (sites.begin(), sites.end()); 
	for (int i = 0; i < sites.size(); ++i)
    {                                                                         
		cout<< sites[i] <<endl;
    } 
	training (sites, 1e-5);
	cout<<endl;
	for (int i = 0; i < sites.size(); ++i)
	{
		cout<< sites[i] <<endl;
	}
	return 0;
}
